package dynamic.barcutting;

import java.util.Arrays;

/**
 * @author 罗俊华
 * @date 2021/7/21 - 9:40 上午
 */
public class DownToTopDynamic {

    /**
     * 使用自底向上的动态规划的好处，
     * 相比自顶向下，省去了递归调用的开销，
     * 在时间复杂度方面有系数上的稍微优势，
     * 但在length很大时，自顶向下很容易发生 outOfStack 错误，
     * 但是自低向上的却不会发生
     *
     * @param lengthMappingProfit
     * @param length
     * @return
     */
    public static int getMaxProfit(int[] lengthMappingProfit, int length) {

        int profit = 0;

        int p2 = 0;


//        加缓存
        int[] cache = new int[length + 1];
//        记录每段钢条长度对应的最优解
        int[] elements = new int[length + 1];

//        最外层的for循环相当于一层从小到大限制，
//        只有在在这个区域内找到其最大收益之后，才能进入下一个区域
        for (int i = 1; i <= length; i++) {

            // 初始化缓存
//            cache[i] = Integer.MIN_VALUE;

            for (int j = 1; j <= i; j++) {

                p2 = getProfitByLength(lengthMappingProfit, j, cache) + cache[i - j];

                if (p2 > profit) {

                    profit = p2;
                    elements[i] = j;
                }
//                profit = Math.max(profit, getProfitByLength(lengthMappingProfit, j, cache) + cache[i - j]);
            }
//          更新缓存，从逻辑上来看，总是先更新缓存之后，才会用到缓存
            cache[i] = profit;
        }

        for (int i = 0; i < elements.length; i++) {
            System.out.print(i + ", ");
        }
        System.out.println("\n"+Arrays.toString(elements));
        return profit;
    }

    /**
     * 如果没有超出长度映射价格表的范围，就用该表的，如果超过了，就用缓存中的
     *
     * @param lengthMappingProfit
     * @param length
     * @param cache
     * @return
     */
    private static int getProfitByLength(int[] lengthMappingProfit, int length, int[] cache) {

        if (length < lengthMappingProfit.length) {
            return lengthMappingProfit[length];
        }

        return cache[length];

    }
}
